package tp;

import java.util.ArrayList;
import java.util.HashSet;

public class Utils {

	private static int size;
	/**
	 * @param node
	 * @return la referencia al nodo de maximo valor del campo index del arbol
	 *         de raiz root
	 */
	public static Node getMax(Node node) {
		if (node == null)
			return null;
		if (node.getRight() == null)
			return node;
		else
			return getMax(node.getRight());
	}

	/**
	 * @param node
	 * @return la referencia al nodo de miniom valor del campo index del arbol
	 *         de raiz root
	 */
	public static Node getMin(Node node) {
		if (node == null)
			return null;
		if (node.getLeft() == null)
			return node;
		else
			return getMin(node.getLeft());
	}

	/**
	 * @param node
	 *            incremente en uno el campo index de todos los nodos del arbol
	 *            de raiz root value = 1: incrementa en 1 los indices value =
	 *            -1: decrementa en 1 los indices
	 */
	public static void correctIndexes(Node node, Node recentlyAdded, int index,
			int value) {
		if (node == null)
			return;

		// si el campo index del elemento actual es mayor
		// o igual a index, debo incrementarlo
		if (node.getIndex() >= index)
			// siempre que no sea el elemento que acabo de ingresar
			// en la posicion index
			if (node != recentlyAdded)
				node.setIndex(node.getIndex() + value);
		// llamadas recursivas para recorrer todo el arbol
		correctIndexes(node.getLeft(), recentlyAdded, index, value);
		correctIndexes(node.getRight(), recentlyAdded, index, value);
	}

	/**
	 * @param node
	 *            : referencia del nodo que debe cambiarse.
	 * @param toChange
	 *            : referencia del nodo por el cual node debe cambiarse.
	 * @param actual
	 *            : referencia al nodo padre del nodo toChange.
	 * @param isMin
	 *            : true ssi toChange es el minimo de los nodos del subarbol
	 *            derecho de node
	 * 
	 *            Al estar parado en el nodo actual, asigna como hijo en la
	 *            referencia donde tenia a toChange al sub-arbol que pueda tener
	 *            toChange (toChange solo puede tener un sub-arbol izquierdo o
	 *            uno derecho, pero nunca ambos, ya que es el nodo con minimo (o
	 *            máximo) indice dentro del sub-arbol con raiz root), e
	 *            intercambia el item y el index de root con el del nodo
	 *            toChange (toChange pasa a ser la nueva raiz del sub-arbol de
	 *            raiz root).
	 */
	public static void exchange(Node node, Node toChange, Node actual,
			boolean isMin) {
		if (actual == toChange) { // caso en q toChange sea hijo directo de node
			node.setInfo(toChange.getInfo());
			node.setIndex(toChange.getIndex());
			if (isMin)
				node.setRight(toChange.getRight());
			else
				node.setLeft(toChange.getLeft());
			return;
		} else if (isMin) // si isMin == true, debo buscar el indice mas chico
			if (actual.getLeft() == toChange) {
				node.setInfo(toChange.getInfo());
				node.setIndex(toChange.getIndex());
				actual.setLeft(toChange.getRight());
			} else
				exchange(node, toChange, actual.getLeft(), isMin);
		else // si isMin == false, debo buscar el indice mas grande
		if (actual.getRight() == toChange) {
			node.setInfo(toChange.getInfo());
			node.setIndex(toChange.getIndex());
			actual.setRight(toChange.getLeft());
		} else
			exchange(node, toChange, actual.getRight(), isMin);
	}

	/**
	 * @param node
	 * @return true iff my node is the root of a binary search tree.
	 */
	public static boolean isBinarySearchTree(Node node) {
		ArrayList<Node> nodeList = new ArrayList<Node>();
		inOrder(node, nodeList);
		return isOrderTree(nodeList);
	}

	/**
	 * @param node
	 * @param list
	 * 
	 *            Charge on the parameter list my tree.
	 */
	public static void inOrder(Node node, ArrayList<Node> list) {
		if (node != null) {
			inOrder(node.getLeft(), list);
			list.add(node);
			inOrder(node.getRight(), list);
		}
	}

	/**
	 * @param list
	 * @return true iff my list is ordered.
	 */
	public static boolean isOrderTree(ArrayList<Node> list) {
		Node previous = list.get(0), next;
		size = list.size() - 1;
		for (int i = 0; i < size; i++) {
			next = list.get(i + 1);
			if (previous.getIndex() + 1 != next.getIndex())
				return false;
			previous = next;
		}
		return true;
	}
	
	/**
	 * @param node
	 * @return true iff all nodes of my tree have data.
	 */
	public static boolean nodesWithDataAndIndex(Node node, int size) {
		if (node == null)
			return true;
		if ((Integer) node.getIndex() == null || node.getInfo() == null || node.getIndex() < 0 || !(node.getIndex() < size))
			return false;
		return nodesWithDataAndIndex(node.getLeft(), size)
				&& nodesWithDataAndIndex(node.getRight(), size);
	}
	
	/**
	 * @param node
	 * @param set
	 * @return true iff node is the root of an acyclic tree.
	 */
	public static boolean isAciclyc(Node node, HashSet<Node> set) {
		if (node == null)
			return true;
		if (!set.add(node))
			return false;
		return isAciclyc(node.getLeft(), set) && isAciclyc(
		node.getRight(), set);
	}

}